package com.zklh.leetcode.structure.uf.use;

import com.zklh.leetcode.structure.uf.UnionFindStructure;
import com.zklh.leetcode.structure.uf.UnionFindStructureV3;

/**
 * @author ：tong nan
 * @date ：Created in 2021/6/8 15:51
 * @description ：合法算式判断器
 * @modifiedBy ：
 */
public class LegalFormulaJudger {

    boolean equationsPossible(String[] equations) {

        UnionFindStructure uf = new UnionFindStructureV3(26);
        // 先联通所有相等的
        for (String equation : equations) {
            if (equation.charAt(1) == '=') {
                uf.union(equation.charAt(0)-'a', equation.charAt(3)-'a');
            }
        }
        // 再看不相等的 是否和相等冲突
        for (String equation : equations) {
            if (equation.charAt(1) == '!') {
                if (uf.connected(equation.charAt(0)-'a', equation.charAt(3)-'a')) {
                    return false;
                }
            }
        }
        return false;
    }
    
}
